import java.util.HashMap;
import java.util.Optional;

//最长回文子串
//https://leetcode.cn/problems/longest-palindromic-substring/description/
public class Test {
    public static void main(String[] args) {
        //
        Solution s = new Solution();
        String sTest = "cbbd";
        String res = s.longestPalindrome(sTest);
        System.out.println(res);

    }
}

//class Solution {
//    public String longestPalindrome(String s) {
//        //
//        HashMap<Integer, Integer> map = new HashMap<>();//<lenght,左index>
//        int i = 0;//中间字符的位置（对称中心）
//        int left = i;
//        int right = i;
//        for(; i < s.length(); i++){
//            while (left >= 0 && right < s.length()){
//                //
//                if(s.charAt(left) == s.charAt(right)){
//                    right++;
//                    left++;
//                }else if(s.charAt(i) == s.charAt(right) && right-i==1){
//                    right++;
//                }else{
//                    break;
//                }
//
//            }
//
//            map.put(right-left-1, left-1);
//        }
//        Optional<Integer> max = map.values().stream()
//                .max(Integer::compare);
//        if (max.isPresent()) {
//            return s.substring(map.get(max), left + max.get() - 1);
//        } else {
//            return "";
//        }
//    }
//}



class Solution {
    public String longestPalindrome(String s) {
        //
        int len = 0;
        int start = 0;
        int end = 0;
        int i = 0;//中间字符的位置（对称中心）

        for(; i < s.length(); i++){
            int left = i;
            int right = i;
            //先扩展奇数长度的子串
            while (left >= 0 && right < s.length()){
                //
                if(s.charAt(left) == s.charAt(right)){
                    right++;
                    left--;
                }else{
                    break;
                }

            }

            int tmpLen = (right -1) - (left + 1) + 1;
            if(tmpLen > len){
                len = tmpLen;
                start = left+1;
                end = right -1;
            }

            left = i;
            right = i+1;
            //再扩展偶数长度的子串
            while (left >= 0 && right < s.length()){
                if(s.charAt(left) ==  s.charAt(right)){
                    left--;
                    right++;
                }else{
                    break;
                }
            }

            tmpLen = (right -1) - (left + 1) + 1;
            if(tmpLen > len){
                len = tmpLen;
                start = left+1;
                end = right -1;
            }


        }
        return s.substring(start, end + 1);
    }
}